﻿#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
#include <vector>
using namespace std;

// 一维数组前缀和
int main()
{
    // 1.读入数据
    int n = 0, q = 0;
    cin >> n >> q;
    vector<long long> arr(n + 1);
    vector<long long> dp(n + 1);
    for (int i = 1; i <= n; ++i)
    {
        cin >> arr[i];
    }
    // 2.预处理前缀和数组
    for (size_t i = 1; i <= n; ++i)
    {
        dp[i] = dp[i - 1] + arr[i];
    }
    // 3.使用前缀和数组
    int l = 0, r = 0;
    while (q--)
    {
        cin >> l >> r;
        cout << dp[r] - dp[l - 1] << endl;
    }

    return 0;
}

//给你一个 n 行 m 列的矩阵 A ，下标从1开始。
//
//接下来有 q 次查询，每次查询输入 4 个参数 x1, y1, x2, y2
//
//请输出以(x1, y1) 为左上角, (x2, y2) 为右下角的子矩阵的和
//第一行包含三个整数n, m, q.
//
//接下来n行，每行m个整数，代表矩阵的元素
//
//接下来q行，每行4个整数x1, y1, x2, y2，分别代表这次查询的参数
int main()
{
    //1.读入数据
    int n = 0, m = 0, q = 0;
    cin >> n >> m >> q;
    vector<vector<long long>> arr(n + 1, vector<long long>(m + 1));
    for (size_t i = 1; i <= n; i++)
        for (size_t j = 1; j <= m; j++)
            cin >> arr[i][j];

    // 2.预处理前缀和矩阵
    vector<vector<long long>> dp(n + 1, vector<long long>(m + 1));
    for (size_t i = 1; i <= n; i++)
        for (size_t j = 1; j <= m; j++)
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + arr[i][j];

    // 3.使用前缀和矩阵
    int x1 = 0, y1 = 0, x2 = 0, y2 = 0;
    while (q--)
    {
        cin >> x1 >> y1 >> x2 >> y2;
        cout << dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1] << endl;
    }

    return 0;
}

//给你一个整数数组 nums ，请计算数组的 中心下标 。
//
//数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。
//
//如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。
//这一点对于中心下标位于数组最右端同样适用。
//
//如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 - 1 。
class Solution
{
public:
    int pivotIndex(vector<int>& nums)
    {
        vector<int> f(nums.size()), g(nums.size());
        // 预处理前缀和后缀和数组
        for (size_t i = 1; i < nums.size(); ++i)
            f[i] = f[i - 1] + nums[i - 1];
        for (int i = nums.size() - 2; i >= 0; i--)
            g[i] = g[i + 1] + nums[i + 1];

        // 判断
        for (size_t i = 0; i < nums.size(); i++)
        {
            if (f[i] == g[i])
                return i;
        }

        return -1;
    }
};


//给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
//
//题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。
//
//请不要使用除法，且在 O(n) 时间复杂度内完成此题。

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n), g(n);
        // 需要将f的第一个和g的最后一个置为1，否则全部为0
        f[0] = g[n - 1] = 1;
        // f 表⽰：[0, i - 1] 区间内所有元素的乘积
        // g 表⽰：[i + 1, n - 1] 区间内所有元素的乘积
        // 预处理前缀积以及后缀积
        for (size_t i = 1; i < n; ++i)
            f[i] = f[i - 1] * nums[i - 1];
        for (int i = n - 2; i >= 0; i--)
            g[i] = g[i + 1] * nums[i + 1];

        vector<int> ret(n);
        // 处理结果数组
        for (size_t i = 0; i < n; i++)
        {
            ret[i] = f[i] * g[i];
        }

        return ret;
    }
};